package euler.p101_150;

import euler.MainEuler;
import euler.helper.Rational;
import euler.helper.SistemasEcuaciones;

public class Euler101 extends MainEuler {

    /*
        If we are presented with the first k terms of a sequence it is
        impossible to say with certainty the value of the next term, as there
        are infinitely many polynomial functions that can model the sequence.

        As an example, let us consider the sequence of cube numbers. This is
        defined by the generating function,
        u(n) = n^3: 1, 8, 27, 64, 125, 216, ...

        Suppose we were only given the first two terms of this sequence.
        Working on the principle that "simple is best" we should assume a
        linear relationship and predict the next term to be 15 (common
        difference 7). Even if we were presented with the first three terms,
        by the same principle of simplicity, a quadratic relationship should be
        assumed.

        We shall define OP(k, n) to be the nth term of the optimum polynomial
        generating function for the first k terms of a sequence. It should be
        clear that OP(k, n) will accurately generate the terms of the sequence
        for n ≤ k, and potentially the first incorrect term (FIT) will be
        OP(k, k+1); in which case we shall call it a bad OP (BOP).

        As a basis, if we were only given the first term of sequence, it would
        be most sensible to assume constancy; that is, for n ≥ 2, OP(1, n) = u(1).

        Hence we obtain the following OPs for the cubic sequence:
        OP(1, n) = 1            1, 1, 1, 1, ...
        OP(2, n) = 7n−6         1, 8, 15, ...
        OP(3, n) = 6n^2−11n+6   1, 8, 27, 58, ...
        OP(4, n) = n^3          1, 8, 27, 64, 125, ...

        Clearly no BOPs exist for k ≥ 4.

        By considering the sum of FITs generated by the BOPs (indicated in red
        above), we obtain 1 + 15 + 58 = 74.

        Consider the following tenth degree polynomial generating function:

        u(n9 = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^10

        Find the sum of FITs for the BOPs.
     */

    public String resolve() {

        int[] poly = new int[]{1,-1,1,-1,1,-1,1,-1,1,-1,1};

        long sumofFITs = 0;

        for (int i = 1; i < poly.length + 1; i++) {

            long[][] matrix = new long[i][i];
            long[] independientes = new long[i];

            for (int j = 0; j < matrix.length; j++) {
                long n = 1;

                for (int k = 0; k < matrix.length; k++) {
                    matrix[j][k] = n;
                    n*=(j+1);
                }

                independientes[j] = evaluar(poly,j+1);
            }

            Rational[] solucion = SistemasEcuaciones.resolverGaussiana(matrix, independientes);

            for (int j = 0; j < poly.length; j++) {
                long FIT = (long)evaluar(solucion,j+1);
                long value = evaluar(poly,j+1);
                if (value != FIT) {
                    sumofFITs+=FIT;
                    break;
                }
            }
        }

        return String.valueOf(sumofFITs);
        // 37076114526
    }

    private static long evaluar(Rational[] solucion, int n) {
        long suma = 0;
        long p = 1;

        for (int i = 0; i < solucion.length; i++) {
            suma+=(solucion[i].getNum() * p);
            p*=n;
        }

        return suma;
    }

    private static long evaluar(int[] poly, long n) {
        long suma = 0;
        long p = 1;

        for (int i = 0; i < poly.length; i++) {
            suma+=(poly[i] * p);
            p*=n;
        }

        return suma;
    }

}
